﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0122_GetIntersectionNode : IAlgorithm
    {
        // 相交链表

        // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item) 
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
        {
            var hashSet = new HashSet<ListNode>();
            while (headA != null || headB != null)
            {
                if (headA != null)
                    if (hashSet.Contains(headA))
                        return headA;
                    else
                    {
                        hashSet.Add(headA);
                        headA = headA.next;
                    }
                if (headB != null)
                    if (hashSet.Contains(headB))
                        return headB;
                    else
                    {
                        hashSet.Add(headB);
                        headB = headB.next;
                    }
            }
            return null;
        }
    }
}
